Digital signatures are used to digitally prove that signed data was sent by a particular entity. Each entity, such as a computer user, derives a set of data known as a key pair. One key of the pair is known as a public key and can be freely distributed. A second key of the pair is known as a private key and the ability of a digital signature to uniquely identify a particular entity depends on how carefully that entity guards its private key. Any data can be “signed” using the private key. More specifically, the data to be signed and the private key are provided as inputs to known mathematical functions. The output of such functions is the digital signature of the data.
The public key can then be used to verify that the data has not changed since it was signed. More specifically, the signed data, the digital signature, and the public key are provided as inputs to known mathematical functions. If the signed data was modified after it was signed, the mathematical functions will so indicate, generally through an inequality of resulting values that would have been equal but for the modification of the data. Given that only the private key could have generated a signature that will be mathematically verified with the corresponding public key, such a mathematical verification of the signature indicates that the data was not changed since it was signed by someone in possession of the private key. If only one entity possesses the private key, the verification of the signature acts to verify that the data was, in fact, sent by that entity, and that it was not modified during transmission.
One commonly used digital signature algorithm is known as the RSA algorithm, borrowing the first letter of the last names of the three individuals credited with its discovery. An RSA public key comprises a “public exponent” commonly designated by the letter “e” and a modulus commonly designated by the letter “n”. An RSA signature “s” of some data, traditionally called a “message” and represented by the variable “m”, can be verified by checking that se mod n is equal to F(m,n), where “F” is an agreed upon padding function.
As the use of digital communications increases, the number of signed messages will likewise increase. Consequently, the time spent verifying signed messages can be of importance, especially because, while a message needs to be signed only once, its signature can be verified multiple times—once by each recipient. As a result, signature verification is performed many more times than message signing.
With the RSA algorithm, signature verification requires the computation of both F(m,n), where “F” is an agreed upon padding function, and se mod n. Of the two expressions, the latter is traditionally more computationally intensive to compute. In fact, se mod n is generally evaluated in a piecemeal fashion using individual modular multiplications and modular squaring. To calculate se mod n directly, and avoid such a piecemeal approach, would, as is known to those skilled in the art, result in the computation of an se term that can be very large, with a resulting loss of performance.